/*用大顶堆作升序排列*/

#include <iostream>
#include <vector>
#include <ctime>
#include <random>
#include <algorithm>

using namespace std;

//交换数组中的两个数
void swap(vector<int> &vec, int i, int j)
{
    int tmp = vec[i];
    vec[i] = vec[j];
    vec[j] = tmp;
}

/*
*@param tree : heap
*@param n ： number of nodes
*@param i : id of node
*给每个子结点排序成为大顶堆
*/
void heapify(vector<int> &tree, int n, int i)
{
    if (i >= n)
        return;
    int leftChild = 2 * i + 1;  //左子结点
    int rightChild = 2 * i + 2; //右子结点
    int max = i;                //假设当前结点为子树最大值
    //将最大值放在子树顶点
    if (leftChild < n && tree[leftChild] > tree[max])
        max = leftChild;
    if (rightChild < n && tree[rightChild] > tree[max])
        max = rightChild;
    if (max != i)
    {
        swap(tree, max, i);
        heapify(tree, n, max);
    }
}

//用vector建立一个堆
void heap_build(vector<int> &vec, int n)
{
    int last_node = n - 1;
    int parent = (last_node - 1) / 2;
    for (int i = parent; i >= 0; i--)
    {
        heapify(vec, n, i);
    }
}

//堆排序
void heap_sort(vector<int> &vec, int n)
{
    heap_build(vec, n);
    //每次循环都会将最大的数放在树顶也就是vec[0]
    for (int i = n - 1; i >= 0; i--)
    {
        swap(vec, i, 0);
        //i在减小的过程中，大于i的位置已经被排序
        heapify(vec, i, 0);
    }
}

int main(void)
{
    vector<int> vec;
    srand(time(0));
    for (int i = 0; i < 8; i++)
    {
        vec.push_back(rand() % 10 + 1);
    }

    std::cout << "排序前：" << '\n';
    for (int i : vec)
    {
        cout << i << "  ";
    }
    std::cout << '\n';

    std::cout << "自制的heap_sort算法排序结果：" << '\n';
    heap_sort(vec,vec.size());
    for (int i : vec)
    {
        cout << i << "  ";
    }
    std::cout << '\n';

    return 0;
}
